#include <iostream>
#include <stack>
#include <string.h>

using namespace std;

class Solution {
public:
    string removeDuplicateLetters(string s) {
        int last_position[26] = {-1};
        memset(last_position, -1, sizeof(last_position));
        for (int i = s.size() - 1; i >= 0; i--) {
            if (last_position[s[i] - 'a'] == -1) {
                last_position[s[i] - 'a'] = i;
            }
        }
        stack<char> stack;
        bool exist[26] = {false};
        for (int i = 0; i < s.size(); i++) {
            if (exist[s[i] - 'a']) {
                continue;
            }
            while (stack.size() > 0 && s[i] < stack.top() && last_position[stack.top() - 'a'] > i) {
                exist[stack.top() - 'a'] = false;
                stack.pop();
            }
            stack.push(s[i]);
            exist[s[i] - 'a'] = true;
        }
        string ans(stack.size(), ' ');
        for (int i = stack.size() - 1; i >= 0; i--) {
            ans[i] = stack.top();
            stack.pop();
        }
        return ans;
    }
};

int main() {
    Solution solution;
    string output = solution.removeDuplicateLetters("ccacbaba");
    cout << output << endl;
    return 0;
}